import java.util.*;

public class Test {
    /*
    题目 1 ：水果篮子
     */
    public int totalFruit(int[] f) {
        int n = f.length;

        Map<Integer, Integer> map = new HashMap<>();

        int len = 0;

        for(int left = 0, right = 0; right < n; right++){
            int in = f[right];
            map.put(in, map.getOrDefault(in, 0) + 1);

            while(map.size() > 2){
                int out = f[left];
                map.put(out, map.get(out) - 1);
                if(map.get(out) == 0){
                    map.remove(out);
                }
                left++;
            }

            len = Math.max(len, right - left + 1);
        }
        return len;
    }

    /*
    题目 2：将 x 减到 0 的最小操作数
     */
    // 问题可以转换成 和为 sum - x 的最长子数组
    public int minOperations(int[] nums, int x) {
        int len = -1;
        int n = nums.length;
        int sum = 0;

        for(int y : nums){
            sum += y;
        }

        int tg = sum - x;
        if(tg < 0){
            return -1;
        }

        int s = 0;

        for(int left = 0, right = 0; right < n; right++){
            s += nums[right];
            while(s > tg){
                s -= nums[left++];
            }
            if(s == tg){
                len = Math.max(len, right - left + 1);
            }
        }

        return len == -1 ? len : n - len;
    }

    /*
    题目 3：子数组最大平均数 I
     */

    public double findMaxAverage1(int[] nums, int k) {

        int n = nums.length;
        int sum = 0;

        for(int i = 0; i < k; i++){
            sum += nums[i];
        }
        double ret = sum;

        int left = 0;
        int right = left + k - 1;

        while(right < n){
            sum -= nums[left++];
            if((right + 1) < n){
                sum += nums[++right];
            }else{
                break;
            }

            ret = Math.max(ret, sum);
        }

        return ret / k;
    }

    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int sum = 0;

        for(int i = 0; i < k; i++){
            sum += nums[i];
        }

        int maxSum = sum;

        for(int i = k; i < n; i++){
            sum = sum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, sum);
        }

        return 1.0 * maxSum / k;
    }

    /*
    题目 4：长度为三且各字符不同的子字符串
     */
    public int countGoodSubstrings1(String ss) {
        char[] s = ss.toCharArray();

        int n = s.length;
        int ret = 0;

        for(int i = 0; i < n - 2; i++){
            int[] hash = new int[26];
            int count = 0;
            for(int j = i;j < n && j < i + 3; j++){
                int index = s[j] - 'a';
                hash[index]++;
                if(hash[index] > 1){
                    break;
                }
                count++;
            }
            if(count == 3){
                ret++;
            }
        }

        return ret;
    }

    // 这道题暴力枚举更快！
    public int countGoodSubstrings(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        int ret = 0;

        for(int i = 2; i < n; i++){
            if(s[i] != s[i - 1] && s[i] != s[i - 2] && s[i - 1] != s[i - 2]){
                ret++;
            }
        }
        return ret;
    }

    /*
    题目 5：学生分数的最小差值
     */
    public int minimumDifference1(int[] nums, int k) {
        Arrays.sort(nums);

        int n = nums.length;

        int left = 0;
        int right = left + k - 1;

        int ret = Integer.MAX_VALUE;
        while(right < n){
            int quo = nums[right++] - nums[left++];
            ret = Math.min(quo, ret);
        }

        return ret;
    }

    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ret = Integer.MAX_VALUE;

        for(int i = 0; i < n - k + 1; i++){
            ret = Math.min(ret, nums[i + k -1] - nums[i]);
        }

        return ret;
    }

    /*
    题目 6：得到 K 个黑块的最少涂色次数
     */
    public int minimumRecolors(String blocks, int k) {
        char[] b = blocks.toCharArray();
        int ret = 0;
        int n = b.length;
        for(int i = 0; i < k; i++){
            ret += b[i] == 'W' ? 1 : 0;
        }

        int count = ret;

        for(int left = 0, right = k; right < n; right++){
            count += b[right] == 'W' ? 1 : 0;
            count -= b[left] == 'W' ? 1 : 0;

            ret = Math.min(ret, count);
            left++;
        }

        return ret;
    }

    /*
    题目 7：找到字符串中所有字母异位词
     */
    public static List<Integer> findAnagrams(String ss, String p) {
        List<Integer> list = new LinkedList<>();
        char[] s1 = ss.toCharArray();
        int n1 = s1.length;

        char[] s2 = p.toCharArray();
        int n2 = s2.length;

        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();

        for(int i = 0; i < n2; i++){
            map2.put(s2[i], map2.getOrDefault(s2[i], 0) + 1);
        }

        int count = 0;

        for(int left = 0, right = 0; right < n1; right++){
            char in = s1[right];
            map1.put(in, map1.getOrDefault(in, 0) + 1);
            if(map1.get(in) <= map2.getOrDefault(in,0)){
                count++;
            }

            while(right - left + 1 > n2){
                char out = s1[left];
                if(map1.get(out) <= map2.getOrDefault(out,0)){
                    count--;
                }
                map1.put(out, map1.get(out) - 1);
                left++;
            }
            if(count == n2){
                list.add(left);
            }
        }
        return list;

    }




}
